package Offer05;

import java.util.*;

/**
 * 最长回文子串:
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 * @author 23737
 * @time 2021.10.20
 */
public class TestTwo {
    public static void main(String[] args) {
        System.out.println(new Solution_TwoAdvanced().longestPalindrome("babad"));
        System.out.println(new Solution_TwoAdvanced().longestPalindrome("bb"));
        System.out.println(new Solution_TwoAdvanced().longestPalindrome("ac"));
//        String s = "ab";
//        String substring = s.substring(0, 2);
//        System.out.println(substring);
    }
}

/**
 * 这种思路是正确的，但是写起来太麻烦了，而且有一半样例过不了
 * 思路：先截取字符串，然后进行检测是否是回文，再将回文字符串和其长度用map储存起来
 * 再将map中的字符串长度进行排序，找到最大的，最后根据最大的长度来返回相应的字符串
 */
class Solution_Two {
    private StringBuilder stringBuilder;

    public String longestPalindrome(String s) {
        if (s.length() == 1) {
            return s;
        }
        if (s.length() == 2) {
            if (check(s)) {
                return s;
            } else {
                return String.valueOf(s.charAt(0));
            }
        }
        //先使用map来存储，key是找到的回文字符串，value记录长度
        Map<String, Integer> map = new HashMap<>();
        String finalString = null;

        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length(); j++) {
                String sonStr = s.substring(i, j);
                boolean check = check(sonStr);
                if (check) {
                    map.put(sonStr, sonStr.length());
                }
            }
        }

        List<Integer> list = new ArrayList<>();
        map.forEach((key, value) -> {
            list.add(value);
        });
        Collections.sort(list);
        Integer maxCount = list.get(list.size() - 1);
        for (String s1 : map.keySet()) {
            Integer integer = map.get(s1);
            if (integer.equals(maxCount)) {
                finalString = s1;
            }
        }

        return finalString;
    }

    public boolean check(String s) {
        stringBuilder = new StringBuilder();
        StringBuilder reverse = stringBuilder.append(s).reverse();
        String s1 = String.valueOf(reverse);
        if (s.equals(s1)) return true;
        else return false;
    }
}

/**
 * 暴力解法
 * 但是会超时
 */
class Solution_TwoAdvanced {
    public boolean isPalindromic(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;
    }

    // 暴力解法
    public String longestPalindrome(String s) {
        String ans = "";
        int max = 0;
        int len = s.length();
        for (int i = 0; i < len; i++)
            for (int j = i + 1; j <= len; j++) {
                String test = s.substring(i, j);
                if (isPalindromic(test) && test.length() > max) {
                    ans = s.substring(i, j);
                    max = Math.max(max, ans.length());
                }
            }
        return ans;
    }
}

/**
 * 小技巧解法：
 * 倒置字符串 然后作比较，相同的就存储
 */
class Solution_Two_2{
    public String longestPalindrome(String s) {
        if (s.equals(""))
            return "";
        String origin = s;
        String reverse = new StringBuffer(s).reverse().toString();
        int length = s.length();
        int[][] arr = new int[length][length];
        int maxLen = 0;
        int maxEnd = 0;
        for (int i = 0; i < length; i++)
            for (int j = 0; j < length; j++) {
                if (origin.charAt(i) == reverse.charAt(j)) {
                    if (i == 0 || j == 0) {
                        arr[i][j] = 1;
                    } else {
                        arr[i][j] = arr[i - 1][j - 1] + 1;
                    }
                }
                /**********修改的地方*******************/
                if (arr[i][j] > maxLen) {
                    int beforeRev = length - 1 - j;
                    if (beforeRev + arr[i][j] - 1 == i) { //判断下标是否对应
                        maxLen = arr[i][j];
                        maxEnd = i;
                    }
                    /*************************************/
                }
            }
        return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
    }
}
